10935. Выбрасывание карт
Имеется колода из n карт, пронумерованных от 1 до n. Карта с номером 1 находится сверху,
карта с номером n – снизу. Следующая
операция повторяется до тех пор, пока колода содержит не менее двух карт:
верхняя карта выбрасывается, после чего
находящаяся наверху карта кладется вниз колоды. Необходимо найти
последовательность выбрасываемых карт и номер карты, которая останется в конце.
Вход.
Каждая строка содержит количество карт n
(n £ 50) в колоде. Последняя строка содержит n = 0 и не обрабатывается.
Выход. Для каждого теста вывести две
строки. Первая строка должна содержать последовательность выбрасываемых карт, а
вторая – номер оставшейся последней карты. Формат вывода показан ниже.
7
19
10
6
0
Пример выхода
Discarded cards: 1, 3, 5, 7, 4, 2
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12,
16, 2, 10, 18,14
Remaining card: 6
Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8
Remaining card: 4
Discarded cards: 1, 3, 5, 2, 6
Remaining card: 4
симуляция
Следует производить моделирование
игры. В качестве структуры данных, которая содержит набор карт, будем
использовать очередь deque. Верхний (первый) элемент колоды удаляем командой
pop_front, вставку карты в конец колоды совершаем командой push_back. Описанную
операцию выбрасывания и перекладывания карт совершаем n – 1 раз.
Оставшаяся единственная карта находится в голове очереди.
Колоду карт будем хранить в
очереди d.
deque<int>
d;
Читаем входное значение n. Очищаем очередь и заполняем ее
последовательно числами от 1 до n.
while(scanf("%d",&n),n)
{
d.clear();
for(i = 1; i <= n; i++)
d.push_back(i);
Процедура выбрасывания карты и
перекладывания вниз колоды верхней карты повторяется n – 1 раз.
printf("Discarded
cards:");
for(i = 1; i
< n; i++)
{
printf("
%d",d[0]); d.pop_front();
d.push_back(d[0]); d.pop_front();
if (i <
n-1) printf(",");
}
Номер последней карты содержится
в голове очереди – в ячейке d[0].
printf("\nRemaining
card: %d\n",d[0]);
}